The problem of intersymbol interference resulting from transmission of data on dispersive communication channels is known and an equalization process is effected on the received signal in order to estimate the individual data symbols which were originally transmitted. Various types of equalizer are know but of particular interest in the present context are so-called Viterbi equalizers based on the Viterbi algorithm, which are a form of maximum likelihood (ML) detector.
Furthermore, for the purpose of forward error correction, data may be convolutionally encoded before it is transmitted. (Forward error correction means that the data is corrected at the receiver without the need for retransmission). A Viterbi detector may also be used for decoding convolutionally encoded data.
In the context of ML detection, a trellis diagram is commonly used to represent the progression of states with the passage of time. It is noted here that the number of states S is given by the equation S=N.sup.c where N is the number of symbols in the data alphabet used and C is the constraint length (i.e. extent of intersymbol interference). Thus for a 2-symbol alphabet and a constraint length of 4 there are 16 possible states.
The term `node` is usually used to designate a particular state at a particular time on a trellis diagram.
The arc or path representing the transition between two states (nodes) adjacent in time is known as a `branch` and the associated `branch metric` is an indication of the likelihood of the particular transition occurring. The `partial path metric` represents the overall probability that a particular partial path to the left of the node under consideration represents the correct sequence of state transitions. The term `partial path` is construed accordingly. This is the meaning of the terms partial path and partial path metric as they are used in the present specification, but the terms `path` and `path metric` may also be used to convey the same meaning. The overall path i.e. the path between the beginning and the end of the trellis which has the maximum path metric is the maximum likelihood path which essentially represents the best estimate of the data symbols actually transmitted.
For the avoidance of doubt, it is emphasized here that the path metric is a numerical value indicating the relative likelihood (probability) of a particular transition taking place. Throughout this specification the convention has been adopted that the maximum path metric represents the maximum likelihood, but depending on the manner in which the path metric is determined the converse may equally hold true, namely that the maximum likelihood may be represented by a minimum path metric. Therefore the term `maximum` as used in this specification must be understood to include `minimum` and likewise the words `larger` and `smaller` (and like terms) must be understood to include their converse meanings, viz `smaller` and `larger` respectively.
In theory a maximum likelihood (ML) or maximum a-posteriori (MAP) detector may be used to calculate the branch metrics for every branch in the trellis diagram and then determine the path metric for every path in the trellis diagram, and finally choose the path for which the overall path metric is a maximum. The sequence of symbols corresponding to this path is the estimate of the symbols actually transmitted. The difficulty with this approach is that the number of paths increases exponentially as the trellis diagram is traversed from left to right.
The Viterbi detector (mentioned earlier) is a computationally more efficient version of a ML detector which exploits the special structure of the detector to achieve a complexity that grows linearly rather than exponentially along the trellis. Hence, a Viterbi detector has the advantage that it requires a constant computation rate per unit time. For each node, the Viterbi detector selects the path having the largest partial path metric, called the `survivor path` for that node. All partial paths other than the survivor path are discarded because any other partial path has by definition a smaller partial path metric, and hence if it replaced the survivor path in any overall path, the path metric would be smaller.
At each stage of the trellis it is not known which node the optimal path must pass through and so it is necessary to retain one survivor path for each and every node. The symbol associated with the survivor path, called the `survivor`, and the associated path metric have to be stored in memory for each node at a stage representing a particular time in order for the algorithm to proceed to the next stage at time increment t+1.
Only when the terminal node of the trellis has been reached is it possible to determine the unique path of maximum likelihood representing the estimation of the symbols actually transmitted. It is only at this stage that the estimated data symbols can be read off by effecting a "trace-back" along the identified maximum likelihood path.
The decisions made by a conventional Viterbi detector are `hard` decisions in the sense that the estimated data symbols are restricted to correspond exactly to the data symbols of the particular alphabet used. For example, in the case of a 2-symbol alphabet the estimated data symbols are in strict binary digitized form (i.e. expressed in terms of only two levels, e.g. 0 and 1).
The known Viterbi detector has the drawback that an appreciable time delay occurs between detection and output. There are two main factors contributing to this delay. Firstly there is the so-called "truncation length" which is the temporal length of the survivor information stored in memory and secondly there is the so-called "trace-back delay" which is the time taken to process the survivor information, i.e. the time between storing the survivor information in memory and outputting the estimated data decisions. The total time delay may typically amount to, say 70 bits which, by way of example, at a bit transmission rate of 270kb/s would correspond to a significant time delay of 0.26ms. This time lag is undesirable in data receivers generally, but is especially detrimental in the case of voice communication applications.
In addition it has to be noted that a Viterbi detector requires substantial memory capacity to store the survivor information.
European patent application EP-A-0,302,330 relates to a method of evaluating metrics for Viterbi decoding of convoluted code signals in which individual path decisions are made for each state by comparing the pair of `opposing` path metrics, i.e. the path metrics associated respectively with two different symbol types [designated M.sub.A (x,k+1) and M.sub.B (x,k+1) in the present application]. For each state the first path metric [M.sub.A (x,k+1)] of the opposing pair is calculated by adding the current branch metric [b(x,k+1.vertline.x.sub.A,k)] relating to a first symbol type [A] to the respective previous partial path metric [M(x.sub.A,k)] and the second path metric [M.sub.B (x,k+1)] of the pair is calculated by adding the current opposed branch metric [b(x,k+1.vertline.x.sub.B,k)], i.e. relating to a second symbol type [B], to the respective previous partial path metric [M(x.sub.B,k)]. The two opposing path metrics are differenced [M.sub.A (x,k+1)-M.sub. B (x,k+1)] to yield a path decision for each state. Thus, in the case of sixteen states, sixteen path decisions (denoted DEC0, DEC1, . . . DEC15 in EP-A-0,302,330) will be made. Although that patent specification is not explicit in this regard, it is assumed that these path decisions are all stored in memory for selection and read back at a subsequent trace-back stage in the conventional manner of a Viterbi decoder. Also, for each state the two opposing path metrics are compared and the minimum value (MSEL0, MSEL1,...MSEL15) is selected for use as the previous partial path metric at the next transition stage of the trellis. A further stage (M-AND and PRE-MI) is provided for comparing all the minimum metrics (MSEL0, MSEL1, . . . MSEL15) and selecting the overall minimum value (MMIN) which is subtracted as an offset from each of the minimum metric values (MSEL0, MSEL1, . . . MSEL15) at each of the sixteen individual stages (viz. at subtractors SUB0, SUB1, . . . SUB15) in a process which may effectively be regarded as normalization. Additionally, the maximum of all the sixteen minimum metric values may be determined. The maximum and minimum values of the complete set of minimum metrics (SEL0, SEL1, . . . SEL15) may be differenced to provide a so-called differential metric which (as mentioned in passing in EP-A-0,302,330) may be used, for example, for synchronization or for phase ambiguity resolution during Viterbi decoding.